package leetcode.digui_huisu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 17. 电话号码的字母组合
 * <p>
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 * <p>
 * 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 * <p>
 * 示例:
 * <p>
 * 输入："23"
 * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
 * <p>
 * 说明:
 * 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
 * <p>
 * 时间复杂度 O(2^n)  暴力解法,回溯法
 * <p>
 * 定义字符串数组,根据index-数字 匹配对应的字符串
 * 使用当前字符串的每一个字母和下一个数字对应的字符串的每一个字母进行组合得到字符串,保存到指定集合中.
 */
public class Solution17 {
    private static List<String> list;

    //表示对应数字所表示的字符串
    private static String[] strs = {
            " ",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"

    };

    public static List<String> letterCombinations(String digits) {
        list = new ArrayList<>();
        if (digits == null || "".equals(digits)) {
            return Collections.emptyList();
        }
        letterCombinations(digits, 0, "");
        return list;
    }

    /**
     * @param digits  数字字符串
     * @param index   当前所处的数字字符串中的索引
     * @param letters 每一次记录的对应字母字符串
     */
    private static void letterCombinations(String digits, int index, String letters) {


        //递归终止条件 digits.length==index  记录当前字符串组合.
        if (index == digits.length()) {
            list.add(letters);
            return;
        }

        //进行循环中递归，记录拼接每一条树的路径  在使用字符串索引时，一定要防止越界
        String substring;
        if (index == digits.length() - 1) {
            substring = digits.substring(index);
        } else {
            substring = digits.substring(index, index + 1);
        }
        int strIndex = Integer.parseInt(substring);
        String str = strs[strIndex];
        for (int i = 0; i < str.length(); i++) {
            letterCombinations(digits, index + 1, letters + str.charAt(i));
        }
    }

    public static void main(String[] args) {
        List<String> list = letterCombinations("");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}
